package 赛码.微众银行.求询问次数;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Alice现在有一个数x，在范围[0,2n)内。
 * 你需要询问Alice一些问题。每次询问有一个数t，Alice会回答你 t&x 是否等于t。
 * 你不能根据已有的回答改变接下来的询问（即询问需要提前想好）。你需要最少询问多少次来保证你能确定x的值。输出答案mod106+3
 *
 * &的意思是位与运算
 *
 * 当且仅当两种方案中有一个询问不同，我们就认为两种方法是不同的。例如询问[1,2]和[1,3]是不同的，
 * [1,2][2,1]也是不同的（尽管他们得到了相同的结果）
 */
public class Main {
    public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        List function = function((int) Math.pow(2, i));
        System.out.println(function1(function.size()));
    }
    public static List function(int a) {//获得约数
        int c=a;
        ArrayList<Integer> integers = new ArrayList<>();
        for(;c>0;c--){
            if(a%c==0&&c!=a){
                integers.add(c);
            }
        }
        return integers;
    }
    private static String function1(int nextInt) {
        BigInteger sum = new BigInteger("1");
        for(int i=1;i<=nextInt;i++){
            BigInteger sum1 = new BigInteger(String.valueOf(i));
            sum = sum.multiply(sum1);
        }
        BigInteger sum2 = new BigInteger("1000003");
        sum = sum.mod(sum2);
        return String.valueOf(sum);
    }

}
